# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 5.n_queens.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2021/12/2 16:42
------------------------------------------

N皇后问题
给定一个 N*N的棋盘，在其中放置 N个皇后，使得他们不能相互攻击。
相互攻击的条件：同列 or 同行 or 同一对角线上

解析：
    该问题和 4.全排列问题差不多，决策树上的每一层表示棋盘上的每一行；
    每个节点可以做出的选择是：在该行的任意一列放置一个皇后
"""
from copy import deepcopy

res = []


def solve_n_queens(nums):
    """
        输入棋盘边长 n,返回所有合法的位置
        '.', 表示空
        'Q', 表示皇后，初始化棋盘
    """
    board = [['.'] * nums for _ in range(nums)]
    backtrack(board, 0)

    for count, data in enumerate(res, 1):
        print(f'{count}'.center(nums * 2, '='))
        to_visual(data)


def backtrack(board, row):
    """
        路径：board中小于 row的那些行都已经成功放置了皇后
        选择列表：第 row行的所有列都是放置皇后的选择
        结束条件：row 超过board的最后一行

        Tips: 这里用 Python中的 list嵌套表达了二维数组，要注意深浅层拷贝问题
    """

    # 触发结束条件
    if row == len(board):
        res.append(deepcopy(board))
        return

    row_len = len(board[row])

    for col in range(row_len):
        # 排除不合法选项
        if not is_valid(board, row, col):
            continue

        # 做选择
        board[row][col] = 'Q'

        # 进入下一行决策
        backtrack(board, row + 1)

        # 撤销选择
        board[row][col] = '.'


def is_valid(board, row, col):
    """
        判断该位置是否可以放皇后
        O ----------------> (col)
        |
        |
        |
        |
        |
      (row)
    """
    board_len = len(board)

    # 检查 [列] 是否有皇后冲突
    for i in range(board_len):
        if board[i][col] == 'Q':
            return False

    # 检查 [右上方] 是否有皇后冲突
    col_right = col
    for row_up in range(row - 1, -1, -1):
        col_right += 1
        if row_up < 0 or col_right >= board_len:
            break

        elif board[row_up][col_right] == 'Q':
            return False

    # 检查 [左上方] 是否有皇后冲突
    col_left = col
    for row_up2 in range(row - 1, -1, -1):
        col_left -= 1
        if row_up2 < 0 or col_left < 0:
            break

        elif board[row_up2][col_left] == 'Q':
            return False

    return True


def to_visual(board):
    """
        将最终结果打印成图
    """
    content = [' '.join(x) for x in board]
    final_content = '\n'.join(content)
    print(final_content)


def copy_demo():
    """
        N皇后问题在 Python中涉及到的深、浅层拷贝问题的相关演示
    """
    nums = 8
    board = [['.'] * nums] * nums
    board[0][0] = 'a'
    to_visual(board)

    """
    out:
        a . . . . . . .
        a . . . . . . .
        a . . . . . . .
        a . . . . . . .
        a . . . . . . .
        a . . . . . . .
        a . . . . . . .
        a . . . . . . .
        
    可见，此处 board的生成方式在 Python中其实是生成了一个真正的list，其它都是对该 list的引用
    """
    print('=' * nums * 2)
    board2 = [['.'] * nums for _ in range(nums)]
    board2[0][0] = 'b'
    to_visual(board2)

    """
    out:
        b . . . . . . .
        . . . . . . . .
        . . . . . . . .
        . . . . . . . .
        . . . . . . . .
        . . . . . . . .
        . . . . . . . .
        . . . . . . . .
        由于 board的生成方式不同，产生的的实际效果不同
    """


if __name__ == '__main__':
    n = 8
    solve_n_queens(8)
    # copy_demo()
